Just posting this for completness:
The problem was in fact that VP_ONLY_SINGLE_LOGIN_ALLOWED was set to true. And that the variable in sametime.ini that allows certain login types to bypass that single login requirment did not have the correct login type.
This is the site we used to determine our login type. There is another site on IBMs page which lists different login type numbers which didn't work (for exmaple for C++ toolkit it listed 1002 for the login type, when in fact 1000 was the login type we needed)
http://www-1.ibm.com/support/docview.wss?rs=203&uid=swg21114318
For more information check
http://publib.boulder.ibm.com/infocenter/sametime/v7r5m1/topic/com.ibm.help.sametime.home.doc/st751serveradmin.pdf
I did a search for “single login” in the pdf